package com.wf.classRoomTest;

import java.util.Arrays;

/**
 * @author mpk
 * @since 2024/6/5 08:53:11
 */
public class HeapSortTest {

    public static void main(String[] args) {

        int[] arr = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};

        heapSort(arr);

        System.out.println(Arrays.toString(arr));
    }

    private static void heapSort(int[] arr) {

        for (int i = arr.length / 2 - 1; i >= 0; i--) //整体形成大根堆
        {
            adjustHeap(arr, arr.length, i);
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            //每次交换大根堆的第一个数和最后一个数
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            //交换后的最后一个数已经放在排序后的最终位置
            //对剩余数重新构造大根堆
            //(只需对根节点构造大根堆，因为根节点以下的子堆早已是局部大根堆了)
            adjustHeap(arr, i, 0);

        }
    }

    //arr : 数组
//n : 数组前n个数的长度。为什么不是数组长度？因为后面的数是已经排好序的，
//	  所以不必再进入二叉堆。这里不理解不要紧，后面堆排序中大家就能明白了。
//i : 从左往右，从下往上第一个非叶结点的数组下标。即 i = n / 2 - 1
 //另外一个重要的点，下面这个函数只是让以某个非叶结点为根的子堆局部构成大根堆，
//而整个数组构成大根堆是循环遍历的结果。

    /**
     *
     * @param arr 数组
     * @param n length 对多少个元素进行调整,数组前n个数的长度。为什么不是数组长度？
     *          因为后面的数是已经排好序的，
     * 	        所以不必再进入二叉堆。这里不理解不要紧，后面堆排序中大家就能明白了。
     * @param i 表示非叶子节点在数组中的索引。即 i = n / 2 - 1
     */
    private static void adjustHeap(int[] arr, int n, int i) {
        int child; //子节点
        int temp;  //存储结点i的值
        //下面这个for循环，temp初始化为arr[i]后便永恒不变了(巧妙1);
        //每轮循环的判断条件是看当前结点是否有左子节点;
        //子节点成为当前结点(巧妙2)，继续向下构造大根堆（因此构造大根堆是一个自顶向下的过程）
        for (temp = arr[i]; i * 2 + 1 < n; ) {
            child = i * 2 + 1;
            //child+1<n 判断右节点是否存在
            if (child + 1 < n) {
                //arr[child] < arr[child + 1] 如果右节点大于子节点 child 转为右节点
                if (arr[child] < arr[child + 1]) {
                    ++child;
                }
            }
            //如果当前节点值小于子节点值,交换
            if (temp < arr[child]) {

                arr[i] = arr[child];

            } else {
                break;
            }

            i = child;
        }
        arr[i] = temp; //temp最终位置，是最后一次赋值来的，而不是一次次交换的结果
    }

}
